package com.lwt.codetop.arrayOrSort;

// 215. 数组中的第K个最大元素

/**
 * 思路：快排的思想，快速选择算法
 * 时间复杂度：O(n)
 */
public class KthLargestElement {
    private static int findKthLargest(int[] nums, int l, int r, int k) {
        if(l >= r){
            return nums[k];
        }
        int x = nums[l + r >> 1];
        int i = l - 1, j = r + 1;
        while (i < j){
            do i ++; while(nums[i] > x);
            do j --; while(nums[j] < x);
            if(i < j){
                int tmp = nums[i];
                nums[i] = nums[j];
                nums[j] = tmp;
            }
        }
        if(k <= j){
            return findKthLargest(nums, l, j, k);
        }else{
            return findKthLargest(nums, j + 1, r, k);
        }
    }

    public static void main(String[] args) {
        int[] nums = {3,2,1,5,6,4};
        int n = nums.length;
        int k = 2;
        // 下标从0开始
        System.out.println(findKthLargest(nums, 0, n - 1, k - 1));
    }

}
